package 链表.双向带头链表;

public class Double_Linked_list {

    private int size;//有效节点的个数
    private DoubleNode head;//头节点地址
    private DoubleNode tail;//尾节点地址

    //头插--普通写法
    /*

    public void addFirst(int val){

        //创建出一个新节点进行插入
        DoubleNode node = new DoubleNode(val);
        //node.val = val;

        if(head == null){
            //此时没有一个节点
           head = tail = node;
        }else{
            node.next = head;
            head.prve = node;
            head = node;
        }
        size++;
    }

     */

    //头插---精简写法
    public void addFirst(int val){
        //这个节点，就是以后新的头节点，它的前驱和后驱就是可以确定的
        DoubleNode node = new DoubleNode(null, val, head);
        if(tail == null){
            //此时链表为空
            tail = node;
        }else{
            head.prve = node;
        }
        //因为不管head为不为口，head都需要后移
        head = node;
        size++;
    }
    //尾插--精简写法
    public void addLast(int val){

        //这个节点，就是以后新的尾节点,它的前驱和后驱就是可以确定的
        DoubleNode node = new DoubleNode(tail,val,null);

        if(head == null){
            //此时没有一个节点
            head = node;
        }else{
           tail.next = node;
        }
        tail = node;
        size++;
    }

    //在任意 index 索引位置上插入 val值
    public void add(int index, int val){
        //判断索引合理
        if(index < 0 || index > size){
            System.out.println("插入的索引有误！");
            return;
        }

        if(index == 0){
            addFirst(val);
        }else if(index == size){
            addLast(val);
        }else{
            //此时才是正在在中间位置插入，而且节点必然有两个。
            DoubleNode cur = node(index);//索引位置的节点
            DoubleNode node = new DoubleNode(cur.prve, val, cur);
            cur.prve.next = node;//待插入节点的上一个节点
            cur.prve = node;
            size++;
        }

    }

    //根据索引值，找到对应节点位置并返回
    private DoubleNode node(int index){
        if(index < (size / 2)){
            DoubleNode x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        }else{
            DoubleNode x = tail;
            for (int i = size - 1; i > index; i--) {
                x = x.prve;
            }
            return x;
        }

    }

    //根据index索引值，查询val中
    public int get(int index){
        if(rangeCheck(index)){
            DoubleNode cur = node(index);
            return cur.val;
        }
        System.out.println("查询的索引值有误");
        return -1;
    }

    //判断索引值是否合法
    private boolean rangeCheck(int index) {
        if(index < 0 || index >= size){
            return false;
        }
        return true;
    }

    //修改索引为 index 位置的节点值，改为 newVal
    //并返回修改前的值
    public int set(int index, int newVal){
        if(rangeCheck(index)){
            DoubleNode cur = node(index);
            int rep = cur.val;//保存要被修改的值
            cur.val = newVal;

            return rep;
        }
        System.out.println("输入修改的索引值有误");
        return -1;
    }

    /**
     * 删除当前的节点 node
     * @return
     */
    private void unlink(DoubleNode node){

        DoubleNode prve = node.prve;//待删除节点前驱
        DoubleNode next = node.next;//待删除节点后继

        //分治思想：前处理前驱节点是连线关系，
        //前驱处理好后再去处理后继的连线关系。

        /**  分治思想的好处：
         * 下面就完成了四种可能遇到的情况：
         * 1. 前空后不空 2.前空后空
         * 3. 前不空后空 4. 前不空后不空
         */

        //先处理前驱
        if(prve == null){
            //说明此时删的是头节点
            head = next;
        }else{
            prve.next = next;
            next.prve = null;//断开
        }
        //然后处理后继连线
        if(next == null){
            //说明此时删的是尾节点
            tail = prve;
        }else{
            next.prve = prve;
            node.next = null;//断开
        }
        size--;
    }

    /**
     * 删除索引为index位置的元素，并且返回删除前的节点 val
     * @return
     */
    public int remove(int index){

        //如果没有参数就不进行删除
        if(size == 0){
            System.out.println("已经没有节点可以删除了~");
            return -1;
        }

        if(rangeCheck(index)){
            DoubleNode cur = node(index);
            int rep = cur.val;
            unlink(cur);
            return rep;
        }
        System.out.println("输入的删除索引有误");
        return -1;
    }

    //头删
    public int removeFirst(){
       return remove(0);
    }

    //尾删
    public int removeLast(){
        return remove(size - 1);
    }

    /**
     * 删除第一个值为 val 的 节点
     * @return
     */
    public void remoValueOnce(int val){
        for (DoubleNode x = head; x != null ; x = x.next) {
            if(x.val == val){
                unlink(x);
                break;
            }
        }
    }

    /**
     * 删除链表中所有为 val 的节点
     * @return
     */
    public void removeAllValue(int val){
        for (DoubleNode x = head; x != null ; ) {

            if(x.val == val){
                DoubleNode cur = x;
                x = x.next;
                unlink(cur);
            }else {
                x = x.next;
            }
        }
    }


    //补充下toString方法
    public String toString(){
        String rep = "";

        for (DoubleNode x = head; x != null; x = x.next) {
            rep += x.val;
            rep += " -> ";
        }
        rep += "NULL";
        return rep;
    }

}

class DoubleNode{

    //保存前驱节点地址
    DoubleNode prve;
    //当前节点的值
    int val;
    //保存后驱节点地址
    DoubleNode next;

    //构造方法
    public DoubleNode(DoubleNode prve, int val, DoubleNode next) {
        this.prve = prve;
        this.val = val;
        this.next = next;
    }
    //无参构造
    public DoubleNode() {
    }
    //一个有参数构造
    public DoubleNode(int val) {
        this.val = val;
    }
}